package or;

//import com.sun.org.apache.xpath.internal.operations.String;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class T0600 {
    char[] s;
    int[][] memo;

    public int findIntegers(int n) {
        s = Integer.toBinaryString(n).toCharArray();
        int m = s.length;
        memo = new int[m][2];
        for (int i = 0; i < m; i++) {
            Arrays.fill(memo[i], -1);
        }
        return dp(0, false, true);
    }


    public int dp(int i, boolean leftIsOne, boolean isLimit) {
        if (i == s.length) {
            return 1;
        }
        if (!isLimit && memo[i][leftIsOne ? 1 : 0] != -1) {
            return memo[i][leftIsOne ? 1 : 0];
        }
        int res = 0;
        int up = leftIsOne ? 0 : isLimit ? s[i] - '0' : 1;
        for (int j = 0; j <= up; j++) {
            res += dp(i + 1, j == 1, isLimit && j == (s[i] - '0'));
        }
        if (!isLimit) {
            memo[i][leftIsOne ? 1 : 0] = res;
        }
//        System.out.println(i + "  " + leftIsOne + "  " + isLimit + "  " + res);
        return res;
    }

    @Test
    public void test() {
        System.out.println(findIntegers(6));
//        System.out.println(1);
//        String string = new String();


    }
}
